UVa/11116 - Babel towers/11116.AC.clean.cpp

   1 /*
   2  Problem: 11116 - Babel towers
   3  (From the UVa Online Judge)
   4
   5  Author: Andrés Mejía-Posada
   6  Date: April 20/2008
   7 */
   8
   9 #include <iostream>
  10 #include <vector>
  11
  12 using namespace std;
  13
  14 const double EPS = 10E-9;
  15
  16 struct disc{
  17   double x, y, r;
  18 };
  19
  20 //Represents a mass "m" with center of mass at point ("x", "y")
  21 struct mass{
  22   double x, y, m;
  23   mass(){}
  24   mass(double X, double Y, double M) : x(X), y(Y), m(M){}
  25 };
  26
  27
  28 //Returns the new mass formed by combining both masses "a" and "b" into a punctual mass.
  29 mass operator | (const mass &a, const mass &b){
  30   mass r;
  31   r.x = (a.x * a.m + b.x * b.m) / (a.m + b.m);
  32   r.y = (a.y * a.m + b.y * b.m) / (a.m + b.m);
  33   r.m = a.m + b.m;
  34   return r;
  35 }
  36
  37 //True if the center of mass of "C" is outside the base of disc "D"
  38 inline bool outside(const mass &c, const disc &d){
  39   return (c.x-d.x)*(c.x-d.x) + (c.y-d.y)*(c.y-d.y) >  d.r*d.r - EPS;
  40 }
  41
  42 int main(){
  43   int n;
  44   while (cin >> n && n){
  45
  46     vector<disc> d(n);
  47     for (int i=0; i<n; ++i){
  48       cin >> d[i].x >> d[i].y >> d[i].r;
  49     }
  50
  51     int k;
  52     bool ok = true;
  53     for (int j=1; j < n && ok; ++j){
  54       mass c(d[j].x, d[j].y, d[j].r * d[j].r);
  55
  56       for (int i=j-1; i >= 0 && ok; --i){
  57         if (outside(c, d[i])){
  58           ok = false;
  59           k = j;
  60         }
  61         c = c | mass(d[i].x, d[i].y, d[i].r*d[i].r);
  62       }
  63     }
  64
  65     cout << (ok?"F":"Unf") << "easible";
  66     if (!ok) cout << " " << k;
  67     cout << endl;
  68
  69   }
  70   return 0;
  71 }
  72